iT邦幫忙

0

LeetCode - 8 String to Integer (atoi)

  • 分享至 

  • xImage
  •  

本篇同步發布於Blog:[解題] LeetCode - 8 String to Integer (atoi)

平台:

LeetCode

題號:

8 - String to Integer (atoi)

題目連結:

https://leetcode.com/problems/valid-palindrome/

題目說明:

        給1個字串s,實作atoi函式,將此字串轉成整數。字串裡可能包含多個非數字字元,像是+號、-號、空白、非數字等。前面遇到空白都略過,直到第一個非空白字元。接著有可選的+號字元或者-號,後面可能接著數字或者其他字元。

在數字之後的其他字元就都排除不理。

如果在空白字元之後的字串,沒有合理的數字或者是空字串或者只有空白,則回傳0。

解析後的數字如果超出32位元整數的上限/下限,則回傳32位元整數的上限/下限。

比如範例輸入s = "   -42",回傳-42

s = "4193 with words",4193後出現非數字字元,所以只需解析前面的數字,回傳4193

s = "words and 987",一開始出現非數字字元,屬於非合理的數字,回傳0

s = "-91283472332",低於32位元整數的下限,所以回傳32位元整數的下限-2147483648

解題方法:

     有2階段的處理流程,第1階段是解析該字串前面是否有無效的整數規則,如下圖1的解析流程。

圖1

第2階段是前面得知是正數或負數,用64位元變數做進位計算,直到字串讀到結尾或者非數字。再判斷long變數有無超出32位元整數的上限/下限。最後回傳轉型32位元整數。

難度為Medium

程式碼 (C++ 與 C#):

#include <iostream>
#include <cstdlib>
using namespace std;

class Solution {
public:
    int myAtoi(string s) {
        int n = s.length();
        bool isPositive = true;
        int i;
        for(i = 0 ; i < n;++i){
            if(s[i] != ' ' && s[i] != '+' && s[i] != '-' && !isdigit(s[i])){
                return 0;
            }
            else if(s[i] == ' '){
                continue;
            }
            else if(s[i] == '+'){
                ++i;
                break;
            }
            else if(s[i] == '-'){
                ++i;
                isPositive = false;
                break;
            }
            else{
                break;
            }
        }

        long long ans = 0;
        for(int j = i; j < n;++j){
            if(!isdigit(s[j])){
                break;
            }

            ans = ans * 10 + (isPositive ? (s[j] - '0') : -(s[j] - '0'));

            if(ans > INT_MAX){
                return INT_MAX;
            }
            else if(ans < INT_MIN){
                return INT_MIN;
            }
        }

        return (int) ans;
    }
};

int main()
{
    Solution sol;
    cout << sol.myAtoi("   -42") << endl;
    cout << sol.myAtoi("4193 with words") << endl;
    cout << sol.myAtoi("words and 987") << endl;
    cout << sol.myAtoi("-91283472332") << endl;
    return 0;
}
using System;

namespace LeetCode8
{
	public class Solution {
	    public int MyAtoi(string s) {
	        int n = s.Length;
	        bool isPositive = true;
	        int i;
	        for(i = 0 ; i < n;++i){
	            if(s[i] != ' ' && s[i] != '+' && s[i] != '-' && !Char.IsDigit(s[i])){
	                return 0;
	            }
	            else if(s[i] == ' '){
	                continue;
	            }
	            else if(s[i] == '+'){
	                ++i;
	                break;
	            }
	            else if(s[i] == '-'){
	                ++i;
	                isPositive = false;
	                break;
	            }
	            else{
	                break;
	            }
	        }
	        
	        long ans = 0;
	        for(int j = i; j < n;++j){
	            if(!Char.IsDigit(s[j])){
	                break;
	            }
	            
	            ans = ans * 10 + (isPositive ? (s[j] - '0') : -(s[j] - '0'));
	            
	            if(ans > Int32.MaxValue){
	                return Int32.MaxValue;
	            }
	            else if(ans < Int32.MinValue){
	                return Int32.MinValue;
	            }
	        }
	        
	        return (int) ans;
	    }
	}
	public class Program
	{
		public static void Main()
		{
			Solution sol = new Solution();
			Console.WriteLine(sol.MyAtoi("   -42"));
		    Console.WriteLine(sol.MyAtoi("4193 with words"));
		    Console.WriteLine(sol.MyAtoi("words and 987"));
		    Console.WriteLine(sol.MyAtoi("-91283472332"));
		}
	}
}

GITHUB位置(C++ 與 C#):

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/1-99/8.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/1-99/8.cs

Reactions


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言